This invention relates to the field of programmable computers. In particular, this invention relates to a reduced instruction set computing machine and language in which there is no need for classical linear addressing and no need for operand decoding.
Most of today""s commercial computing devices and programming languages are built upon the foundation of the von Neumann Machine. The von Neumann Machine, named after mathematician John von Neumann, defines a class or an architecture for electrical computing devices. The von Neumann Machine solves algorithmically defined problems by repeatedly performing a cycle of operations. Each computer built according to this architecture has an instruction set which defines the available operational codes (xe2x80x9copcodesxe2x80x9d) for a given programming language and system.
The von Neumann Machine is generally characterized by a Central Processing Unit (xe2x80x9cCPUxe2x80x9d) containing an Arithmetic Logic Unit (xe2x80x9cALUxe2x80x9d), and a memory. In general terms, the machine operates by repeating a cycle of events. First, an instruction is fetched from memory. Each instruction includes both an opcode and an operand. The opcode is an instruction to the CPU directing a certain operation to be performed. The operand is the data on which the ALU operates. The operand may be the data itself or it may provide an address from which the data can be retrieved. After fetching an instruction, the CPU fetches the necessary data from memory. Then the CPU, specifically the ALU, executes the opcode on the data. The results of the operation are stored in memory and operation of the machine then returns to the first step to fetch the next instruction. This has been the model underlying electronic computers for more than 50 years.
Modem computers developed up until the mid-1980""s are commonly called Complex Instruction Set Computing (xe2x80x9cCISCxe2x80x9d) machines. CISC machines have relatively large instruction sets including complex, multi-cycle instructions. A large, complex instruction set allows for the development of relatively compact code as each single instruction can actually represent multiple operations by the CPU. The compactness of the code or program was particularly important during this period because of the high cost memory. The downside to the compact code of CISC machines, however, is that significant processing time is consumed by the decoding of these complex instructions. The term xe2x80x9cdecodingxe2x80x9d refers to the process carried out by the CPU of reading or parsing each instruction and converting each instruction into language that can be utilized at the hardware level of the machine to perform the requested operations. It is the xe2x80x9cmicrocodexe2x80x9d of a CISC machine that effectively translates between a human-readable instruction and an instruction executable by the electronic hardware. Also part of the decoding process is operand decoding which involves the identification, location and retrieval of the data to be operated on by the instruction. Complex decoding takes processing time and limits the performance available with CISC machines.
Beginning in the mid-1980""s, corporate and university researchers began developing Reduced Instruction Set Computing (xe2x80x9cRISCxe2x80x9d) machines and methodologies. Researchers found that the vast majority of the operations performed by a CPU could be covered by a relatively small set of instructions. RISC computers were developed to optimize the operation of that small instruction set by hard-wiring those frequently used operations in the hardware. More complex operations were, unlike with CISC computers, simulated in software instead of being wired into the CPU itself. The code resulting from the use of a smaller instruction set is less compact than that of a CISC machine but is processed much more quickly than the equivalent code in a CISC machine. Less compact code is less of a problem for the design of modem computers as the cost of memory has been reduced dramatically and continues to fall.
The basic operation of a RISC computer is the same as a CISC computer. An instruction is fetched from memory and decoded. Each instruction includes an opcode and an operand. The instructions in a RISC computer are typically of a fixed length. Each instruction is typically one word long whereas in a CISC computer the instruction length might be one word or it might be two, three or more words. Other RISC characteristics including more structured and efficient memory access, pipe-lined execution and the lack of microcode contribute to an increased processing speed for RISC machines as compared to CISC machines.
Even the most powerful RISC computers, however, are limited by the requirements of linear addressing and operand decoding. A program of an existing computer operates through the successive execution of each line or step in the program. At the completion of each step, the program execution continues to the next step. The current location in the program is determined by a program counter that, in effect, successively counts through the memory locations in which the program is stored. A decision step in the program can cause the program counter to jump to a different location or address in the program memory. Once the step at the new location is executed, the program counter again continues its successive incrementing through the steps of the program.
Just as each program step is stored at an addressed memory location, so is each piece of data individually addressed. The CPU of current computers only executes operations on data that is in memory or registers accessible to the CPU. The data must be retrieved from memory and stored in a register. so that the CPU can utilize the data in the execution of an instruction. Every time a CISC or RISC machine decodes an instruction""s operand, the operand must be translated to a memory location, the memory location must be located, and the data residing at that memory location must be copied to a register. The CPU is then able to execute the opcode on the data copied in a register. Each of the above steps consumes processing cycles or xe2x80x9cCPU timexe2x80x9d.
There exists a need for a computer with no need for addressing in the linear sense described with respect to existing computers. There exists a further need for a computer with no need for operand decoding. There is a further need for a computer that does not require the loading of data from memory to CPU registers or the storing of data from CPU registers to memory.
This invention concerns a parameterless programming language and machine for optimally implementing the language. The language and machine utilize a multiply dimensioned code space and a multiply dimensioned data space to create a xe2x80x9cparameterless computerxe2x80x9d. The parameterless computer has no need for addressing and no need for operand decoding as all operands are implicit. There is no data loading from memory or data storing to memory as the data is operated on in the data space where it resides. The state of the computer is defined not only by the data and the code but also by the direction of a code pointer and a data pointer. The result is a computing environment where instruction execution speed approaches or equals clock speed.
A parameterless computer includes a code space and a data space. A code space contains the instructions for operating the parameterless computer. The data space contains the data of a parameterless computer. The code space may be separate from the data space or may be common with the data space. A code pointer is defined by both a position and a direction within the code space. The code pointer navigates through the code space according to the instructions encountered by the code pointer in the code space. A data pointer is defined by both a position and a direction within the data space. The data pointer navigates through the data space according to the executed instructions and the state of the data in the data space. The state of the parameterless computer at any given time is determined by the position and direction of the code pointer within the code space and the position and direction of the data pointer within the data space.
The code space and the data space are characterized by two measures. One is the dimension of the space. A code or data space can be n-dimensional. The other characteristic used to describe the code and data space is the type of tiling where the instructions or the data are stored one per tile. The combination of the dimensions and tiling of a space (code or data) determines the specific instructions used to navigate the code and data pointers. For example, in a three-dimensional code space using cubic tiles, each cube, i.e., each instruction in the code space, can be accessed from six different directions. Therefore, the instruction set includes instructions for moving the code pointer through the code space in any of six different directions. Alternatively, a three-dimensional code space might be populated with pyramidal polyhedron tiles. Assuming four-sided pyramidal polyhedrons, each instruction in the code space can be accessed from four different directions. Therefore the instruction set for this example includes instructions for moving the code pointer through the code space in any of the four different directions. The data space and the code space are both described in terms of dimensions and tiling.
Various instruction sets can be devised for navigating the code and data pointers within their respective spaces. The instruction sets enable directional travel of the pointers along paths in the code space and data space. The instruction sets include, for example, instructions for rotating the code and data pointers two different directions and instructions to increment the data pointer to a next location and to invert the current bit in the data space.
One instruction set also permits jump situations in which the code pointer or data pointer can be moved from one location in its space to a different and remote location in its space. This instruction set includes instructions to push current locations of the data or code space onto a stack and to pop those locations off at a later time to return the pointers there.
Code is arranged to optimize its reusability in the parameterless computer of the present invention. In a two-dimensional code space with square tiling, each instruction can be approached by a code pointer moving in any of the four directions possible in a two-dimensional, square tiled space. This means that a single instruction or group of instructions can be used in different directions of code execution to produce different results. Code can be reused as in the traditional sense of a loop of code execution or code can be reused in an entirely unrelated fashion. The small instruction set of the parameterless computer of the present invention increases the probability of reusing code. Code reuse is particularly advantageous and possible since there are no operands associated with the instructions to limit the reuse of code.
An exception handler can be defined in the code space to prevent errant code from running amok through the code space. The exception handler forms a boundary or guardrail of instructions around an isolated code space. Errant code is prevented from escaping the isolated code space absent predictable and predefined exit and exception handling.